#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e6 + 5, MOD = 1e5 + 3;

int n, m, dist[N], cnt[N];
vector<int> ph[N];  // 邻接表存储无向图

void bfs() {
    queue<int> q;
    dist[1] = 0;
    cnt[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // 遍历所有相邻节点
        for (int v : ph[u]) {
            if (dist[v] == -1) {  // 首次访问v，发现更短路径
                dist[v] = dist[u] + 1;  // 无权图距离+1
                cnt[v] = cnt[u];        // 路径数继承自u
                q.push(v);
            } else if (dist[v] == dist[u] + 1) {  // 发现等长路径
                cnt[v] = (cnt[v] + cnt[u]) % MOD;  // 累加路径数，及时取模
            }
        }
    }
}

int main() {
    // 输入优化：关闭cin同步流（比scanf更快）
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    memset(dist, -1, sizeof(dist));
    for (int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        ph[x].push_back(y);
        ph[y].push_back(x);
    }
    bfs();
    for (int i=1; i<=n; ++i)
        cout << (dist[i] == -1 ? 0 : cnt[i]) << '\n';  // 用'\n'比endl快

    return 0;
}